package 面试2025.菜鸟;

import java.util.*;
import java.util.concurrent.*;

/**
 * 问题：设计一个并发查找，输入为1000个数字
 * 第一步，按照下标，每100个作为一组，并发排序，寻找本组中最大的；
 * 第二步，同步等待前面并发routine都结束，再从1000/100 个结果中，找出最终最大的数字；
 */
public class 并发编程 {
    // 线程池，固定10个线程
    private static final ThreadPoolExecutor pool = new ThreadPoolExecutor(
            10, 10, 0L, TimeUnit.MILLISECONDS,
            new LinkedBlockingQueue<>(),
            new ThreadPoolExecutor.CallerRunsPolicy()
    );

    public static void main(String[] args) {
        // 生成测试数据：1000个随机数
        int[] testData = generateTestData(1000);
        System.out.println("生成了1000个随机数，正在并发查找最大值...");

        // 执行并发查找
        int maxValue = findMaxConcurrently(testData);

        // 输出结果
        System.out.println("最终最大值是: " + maxValue);

        // 验证结果（单线程计算最大值进行对比）
        int verifyMax = findMaxSingleThread(testData);
        System.out.println("验证结果（单线程计算）: " + verifyMax);
        System.out.println("结果" + (maxValue == verifyMax ? "正确" : "错误"));

        // 关闭线程池
        pool.shutdown();
    }

    /**
     * 并发查找最大值
     */
    public static int findMaxConcurrently(int[] data) {
        int groupSize = 100;
        int groupCount = data.length / groupSize;
        int[] maxArr = new int[groupCount];

        // 存储每个线程的Future
        List<Future<Integer>> futures = new ArrayList<>();

        // 将数据分组，提交到线程池
        for (int i = 0; i < groupCount; i++) {
            final int groupIndex = i;
            int start = i * groupSize;
            int end = start + groupSize;

            // 提取子数组
            int[] subArray = Arrays.copyOfRange(data, start, end);

            // 提交任务到线程池
            Callable<Integer> task = new Callable<Integer>() {
                @Override
                public Integer call() {
                    // 排序子数组
                    quickSort(subArray);
                    // 返回最大值（排序后最后一个元素）
                    int max = subArray[subArray.length - 1];
                    System.out.println("第" + (groupIndex + 1) + "组最大值: " + max);
                    return max;
                }
            };

            futures.add(pool.submit(task));
        }

        // 等待所有任务完成并收集结果
        try {
            for (int i = 0; i < futures.size(); i++) {
                maxArr[i] = futures.get(i).get(); // 阻塞等待任务完成
            }
        } catch (Exception e) {
            System.err.println("线程执行出错: " + e.getMessage());
            e.printStackTrace();
        }

        // 从各组最大值中找到最终最大值
        return findMax(maxArr);
    }

    /**
     * 查找数组中的最大值
     */
    private static int findMax(int[] arr) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int i = 0;i < arr.length;i++){
            queue.offer(arr[i]);
        }
        return queue.peek();
    }

    /**
     * 快速排序实现
     */
    public static void quickSort(int[] arr) {
        Random rnd = new Random();
        partition(arr, 0, arr.length - 1, rnd);
    }

    private static void partition(int[] arr, int l, int r, Random rnd) {
        if (r - l <= 0) {
            return;
        }
        // 随机选择基准元素
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr, l, p);

        int v = arr[l];
        int lt = l;         // arr[l+1..lt] < v
        int i = lt + 1;     // arr[lt+1..i-1] == v
        int gt = r + 1;     // arr[gt..r] > v

        while (i < gt) {
            if (arr[i] < v) {
                swap(arr, i, lt + 1);
                i++;
                lt++;
            } else if (arr[i] > v) {
                swap(arr, i, gt - 1);
                gt--;
            } else { // arr[i] == v
                i++;
            }
        }
        swap(arr, l, lt);

        // 递归排序
        partition(arr, l, lt - 1, rnd);
        partition(arr, gt, r, rnd);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 生成测试数据
     */
    private static int[] generateTestData(int size) {
        int[] data = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            data[i] = random.nextInt(10000); // 生成0-9999的随机数
        }
        return data;
    }

    /**
     * 单线程查找最大值，用于验证结果
     */
    private static int findMaxSingleThread(int[] data) {
        int max = data[0];
        for (int num : data) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
}
